/**
 * 
 */
package tree.passed2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

import tree.LevelByLevelTraversal;
import tree.Node;

/**
 * @author Michael
 * http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html
 * Serialization/Deserialization of a Binary Tree
 *
 */
public class ReconstructBT {

	// pre order to construct BT by adding sentinel '#'
	public static String writeBT(Node<Integer> root) {
		if (root == null)
			return null;
		
		StringBuilder sb = new StringBuilder();
		Stack<Node<Integer>> stack = new Stack<Node<Integer>>();
		stack.add(root);
		while (!stack.isEmpty()) {
			Node<Integer> node = stack.pop();
			sb.append(node.value).append(',');
			if (node.right != null) {
				stack.push(node.right);
			}
			else {
				sb.append('#').append(',');
			}
			
			if (node.left != null) {
				stack.push(node.left);
			}
			else {
				sb.append('#').append(',');
			}
		}
		
		return sb.toString();
	}
	
	public static void writeBTRecursive(Node<Integer> root, StringBuilder sb) {
		if (root == null)
			sb.append("#,");
		
		sb.append(root.value).append(',');
		writeBTRecursive(root.left, sb);
		writeBTRecursive(root.right, sb);
	}
	
	public static Node<Integer> readBT(String str) {
		String[] arr = str.split(",");
		List<String> list = new LinkedList<String>();
		for (String s : arr) {
			list.add(s);
			System.out.printf("%s ", s);
		}
		System.out.println();
		return readBTHelper(list);	
	}
	
	public static Node<Integer> readBTHelper(List<String> list) {
		if (list.isEmpty())
			return null;
		
		String s = list.get(0);
		if (s.equals("#")) {
			list.remove(0);
			return null;
		}

		Node<Integer> node = new Node<Integer>(Integer.valueOf(s));
		list.remove(0);
		node.left = readBTHelper(list);
		node.right = readBTHelper(list);
		
		return node;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		List<String> list = new LinkedList<String>();
		// pre-order	30 10 50 # # # 20 45 # # 35 # #
		list.add("30");
		list.add("10");
		list.add("50");
		list.add("#");
		list.add("#");
		list.add("#");
		list.add("20");
		list.add("45");
		list.add("#");
		list.add("#");
		list.add("35");
		list.add("#");
		list.add("#");
		
		String str = "30,10,50,#,#,#,20,45,#,#,35,#,#";
		
		//LevelByLevelTraversal.traverseByLevel(readBSTInsert(list));
		LevelByLevelTraversal.traverseByLevel(readBT(str));

	}
	
	/**
	 * 
	 */
	public ReconstructBT() {
		// TODO Auto-generated constructor stub
	}

}
